#include <stdio.h>
#include <stdlib.h>

#include "bintree.h"

int depth(bnode *p, char c);
int main()
{
    bnode *p;
    char c;
    printf("Please enter Extended binary tree: ");
    p = creat();
    printf("Please enter the data: ");
    fflush(stdin);
    scanf("%c", &c);
    printf("The depth is: ");
    printf("%d",depth(p,c));
    return 0;
}

int depth(bnode *p, char c)
{

    int k=1,flag=1;
    bnode *q;
    sqstack L1,L2;
    init(&L1);
    init(&L2);
    push(&L1,p);
    while(!empty(&L1)||!empty(&L2))
    {
        if(flag==1)
        {
            while(!empty(&L1))
            {
                q=pop(&L1);
                if(q->data==c)  return k;
                if(q->lch!=NULL)    push(&L2,q->lch);
                if(q->rch!=NULL)    push(&L2,q->rch);
            }
            k++;
            flag=0;
        }else if(flag==0)
        {
            while(!empty(&L2))
            {
                q=pop(&L2);
                if(q->data==c)  return k;
                if(q->lch!=NULL)    push(&L1,q->lch);
                if(q->rch!=NULL)    push(&L1,q->rch);
            }
            k++;
            flag=1;
        }
    }
    return k = -1;
}
